#include<cstdio>
#include<cstring>
#include<algorithm>
#define INF 0x3f3f3f3f
using namespace std;
typedef long long LL;
typedef double db;
inline int read()
{
	int x=0,f=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') { if(ch=='-')f=-1; ch=getchar(); }
	while(ch>='0'&&ch<='9') { x=(x<<1)+(x<<3)+ch-'0'; ch=getchar(); }
	return x*f;
}
const int MAXN=1e7+10;
int n,m,pri[MAXN],mu[MAXN],tot;
bool ispri[MAXN];
LL f[MAXN],ans;
void cal_prime_mu()
{
	mu[1]=1;
	for(int i=2;i<=int(1e7);++i)
	{
		if(!ispri[i])
		{
			pri[++tot]=i;
			mu[i]=-1;
		}
		for(int j=1;j<=tot&&i*pri[j]<=int(1e7);++j)
		{
			ispri[i*pri[j]]=true;
			if(i%pri[j]==0)
			{
				mu[i*pri[j]]=0;
				break;
			}
			mu[i*pri[j]]=-mu[i];
		}
	}
	for(int i=1;i<=tot;++i)
		for(int j=1;j*pri[i]<=int(1e7);++j)
			f[j*pri[i]]+=mu[j];
	for(int i=1;i<=int(1e7);++i)f[i]+=f[i-1];
	return;
}
int main()
{
	int T=read();
	cal_prime_mu();
	while(T--)
	{
		n=read();m=read();
		if(n>m)swap(n,m);
		ans=0;
		for(int l=1,r;l<=n;l=r+1)
		{
			r=min(n/(n/l),m/(m/l));
			ans+=(f[r]-f[l-1])*(n/l)*(m/l);
		}
		printf("%lld\n",ans);
	}
	return 0;
}
